In this paper, we give an algorithm which, given a set F of at most (n - 1) - k faulty nodes, and two sets S = {s1,..., sk} and T = {t1,..., tk}, 1 k n - 1, of nonfaulty nodes in n-dimensional star graphs Gn, finds k fault-free node disjoint paths si tji, where (j1,..., jk) is a permutation of (1,..., k), of length at most d(Gn) + 5 in O(kn) optimal time, where d(Gn) = 3(n-1)/2 is the diameter of Gn.

In this paper, we give an algorithm which, given a set F of at most n-k faulty nodes, and two sets S={s1, , sk} and T = {t1,, tk}, 1kn, of non-faulty nodes in n-dimensional hypercubes Hn, finds k fault-tree node disjoint paths sitje, where (j1, , Jk) is a permutation of (1, , k), of length at most n + k in O(kn log k) time. The result of this paper implies that n disjoint paths of length at most 2n for set-to-set node disjoint path problem in Hn can be found in O(n2 log n) time.

In this paper, we study the following node-to-node fault tolerant routing problem: In the presence of up to n-1 faulty nodes, find a fault-free path which connects any two non-faulty nodes s and t in an n-connected graph. For node-to-node fault tolerant routing in n-dimensional hypercubes Hn, we give an algorithm which finds a fault-free path s t of length at most in O(n) time, where d(s, t) is the distance between s and t. We also show that a fault-free path s t in Hn of length at most d(s, t)2i, 1i, can be found in time. For node-to-node fault tolerant routing in n-dimensional star graphs Gn, we give an algorithm which finds a fault-free path s t of length at most min{d(Gn)3, d(s, t)6} in O(n) time, where is the diameter of Gn. It is previously known that, in Hn, a fault-free path s t of length at most d(s, t) for d(s, t)n and at most d(s, t)2 for d(s, t)n can be found in O(d(s, t)n) time, and in Gn, a fault-free path s t of length at most min{d(Gn)1, d(s, t)4}can be found in O(d(s, t)n) time. When the time efficiency of finding the routing path is more important than the length of the path, the algorithms in this paper are better than the previous ones.

In general, message passing multiprocessors suffer from communication overhead and shared memory multiprocessors suffer from memory contention. Also, data I/O overhead limits performance. In particular, computer vision tasks that require massive computation are strongly affected by these disadvantages. This paper proposes new parallel architectures for computer vision, a Flexibly (Tightly/Loosely) Coupled Multiprocessor (FCM) and a Flexibly Coupled Hypercube Multiprocessor (FCHM) to alleviate these problems. FCM and FCHM have a variable address space memory in which a set of neighboring memory modules can be merged into a shared memory by a dynamically partitionable topology. FCM and FCHM are based on two different topologies: reconfigurable bus and hypercube. The proposed architectures are quantitatively analyzed using computational models and parallel vision algorithms are simulated on FCM and FCHM using the Intel's Personal SuperComputer (iPSC), a hypercube multiprocessor, showing significant performance improvements over that of iPSC.

This paper proposes parallel VLSI processors for robotics based on multiple processing elements organized around multiple bus interconnection networks. The advantages of multiple bus interconnection networks are generality, simplicity of implementation and capability of parallel communications between processing elements, therefore it is considered to be suitable for parallel VLSI systems. We also propose the optimal scheduling formulated in an integer programming problem to minimize the delay time of the parallel VLSI processors.

The Batcher banyan network is well known as a non-blocking switching fabric. However, it is conflict free only when there is no packets for the same destination. To cope with the arbitrary combination of packets, an additional network or special control sequence which causes the increase of the hardware or performance degradation is required. A Batcher Double Omega network with Combining (BDOC) is an elegant solution of this problem. It consists of a Batcher sorter and two double sized Omega networks. Like in the Batcher banyan network, packets are sorted by the destination label in the Batcher sorter. In the first Omega network called the distributer, a packet is routed by a tag corresponding to the sum of the label at the output of the Batcher sorter and the destination label. In the second (Inverse) Omega network called the concentrator, the original destination label is used as the routing tag, and packets are routed without any conflict. The BDOC is useful for an interconnection network to connect processors and memory modules in multiprocessor. Unlike conventional multistage interconnection networks for multiprocessors, packets are transferred in a serial and synchronized manner. The simple structure of the switching element enables a high speed operation which reduces the latency caused by the serial communication. Using the pipelined circuit switching, the address and data packets share the same control signal, and the structure of the switching element is much simplified. Moreover, packets combining which avoids the hot spot contention is realized easily in the concentrator.